Algorithims Heap Project

Hannah Butsko, Emma Horton, Arianne Pozzi, Matthew Wilcox

Purpose

  • Process Student Applications
  • Prioritize them based on various criteria
  • Make admission offers to most qualified/preferred candidates

Max Heap Implemenation

def max_heap(lst, value):
    lst.append(value)  # Add the new value to the end of the heap
    idx = len(lst) - 1  # Get the index of the newly added element

    # Moving the newly added element up the tree as long as it's greater
    # than its parent, maintaining the max heap property
    while idx > 0:
        parent_index = (idx - 1) // 2
        if lst[idx] > lst[parent_index]:
            lst[idx], lst[parent_index] = lst[parent_index], lst[idx]
            idx = parent_index
        else:
            break

Pop max heap implementation

def pop_max_heap(lst):
    # Checking if list is empty
    if not list:
        return "The array is empty"

    # Checking if there is only one element in the list
    if len(lst) == 1:
        return lst.pop()

    # Maximum element
    max_elem = lst[0]
    # Last element
    last = lst.pop()

    if lst:
        # Moving the last element to the root position
        lst[0] = last
        index = 0
        n = len(lst)

        # Restore the tree by bringing down the element
        while True:
            left = index * 2 + 1
            right = index * 2 + 2
            largest = index

            # Comparing the largest value to the left child
            if left < n and lst[largest] < lst[left]:
                largest = left

            # Comparing the largest value to the right child
            if right < n and lst[largest] < lst[right]:
                largest = right

            # Checking if largest index has been changed
            # No need to swap elements or call function recursively if largest element was not changed
            if largest != index:
                # Swapping the values of the parent with the largest element
                lst[largest], lst[index] = lst[index], lst[largest]
                index = largest
            else:
                break

    # Returning the maximum element that was removed
    return max_elem

Function that organizes student payload into a dictionary

We organized each student into a dictionary to use within the functions to retain all of the students data while assigning a priority

def student_data(name, student_type, computer_science, math, year, orientation_day, email, street, city, state, zip_code):
    return {"name": name,
            "student_type": student_type,
            "computer_science": computer_science,
            "math": math,
            "year": year,
            "orientation_day": orientation_day,
            "email": email,
            "Street Address": street,
            "City": city,
            "State": state,
            "ZIP Code": zip_code}

Prioritizing each student

def priority(payload, idx):
    lst_priority = [
        1 if payload["student_type"] == "Graduate" else 0,
        1 if payload["computer_science"] is True else 0,
        1 if payload["math"] is True else 0,
        payload["year"],  # Closer students are graduating - higher the priority
        -payload["orientation_day"],
        # Reversing the orientation day value to give priority to students that register earlier
        idx  # Unique identifier of each student
    ]

    return lst_priority

Processing each student and admitting by priority criteria

def process_admissions(payload):
    lst = []  #
    admitted_students = []  # Initialize a list for admitted students

    # Enumerating through student requests and prioritizing them
    for idx, student in enumerate(payload):
        priority_student = priority(student, idx)
        max_heap(lst, priority_student)  # Adding every priority to our max heap

    # Admitting students up to a limit 25 based on max heap priorities
    while len(admitted_students) < 25 and len(lst) > 0:
        _, computer_science, math, year, orientation_day, idx = pop_max_heap(lst)
        admitted_students.append(idx)

    return admitted_students

Making offers to admitted students if places become available

def make_offers(payload, admitted_students, dropouts):
    offers = []

    # Checking for admitted students who haven't dropped the class
    for idx, request in enumerate(payload):
        if idx in admitted_students and idx not in dropouts:
            offers.append(request)

    # Filling empty spots with the most qualified students
    while len(offers) < 25:
        # Checking for the next most qualified student who hasn't been previously admitted
        next_student = None
        for index, request in enumerate(payload):
            if index not in admitted_students and index not in dropouts:
                if next_student is None or priority(request, index) > priority(next_student, index):
                    next_student = request

        # If no more qualified students are available, break the loop
        if next_student is None:
            break

        # Marking the student as admitted and add them to the offers list
        admitted_students.append(payload.index(next_student))
        offers.append(next_student)

    return offers

Make a random fake data set of size n

Using the faker package we built a function to create random students to populate our school to test our functions in createing priority queues.

def random_student_admission(size=40):
    # Initialize Faker
    fake = Faker()
    # Create list of student_data dicts
    student_list = []
    for individual in range(0, size):
        name = fake.name()
        student_type = np.random.choice(['Undergraduate', 'Graduate', 'Auditor'])
        computer_science = np.random.choice([True, False])
        math = np.random.choice([True, False])
        year = np.random.randint(0, 5)
        orientation = np.random.randint(1, 6)
        fake_email = fake.free_email()
        fake_address = fake.street_address()
        fake_city = fake.city()
        fake_state = fake.state()
        fake_zip = fake.postcode()
        student_list.append(
            student_data(name, student_type, computer_science, math, year, orientation, fake_email, fake_address, fake_city, fake_state, fake_zip))

    return student_list

Create Admited Sutdents List

We first create a list of admited students. We select the size of our class and generate a random class of that size. In this case we do 38/

Create Admited Sutdents List

We then process them through admissions leaving us with a table of admitted students.

                  name   student_type  computer_science   math  year  \
0        Sierra Thomas       Graduate              True  False     4   
1        Valerie Berry       Graduate              True   True     2   
2       Mallory Nelson  Undergraduate             False  False     4   
3        David Summers  Undergraduate              True   True     4   
4        Angela Burton       Graduate             False  False     2   
5       Michael Nelson       Graduate              True   True     4   
6      Melissa Kennedy        Auditor             False  False     2   
7            Paul Cook        Auditor             False  False     2   
8        Robert Chavez  Undergraduate             False  False     2   
9     Brandon Castillo        Auditor             False   True     2   
10     Michael Burgess  Undergraduate              True   True     4   
11        Jorge Miller       Graduate              True  False     3   
12      Dawn Gillespie       Graduate              True  False     4   
13       Sandra Hansen       Graduate             False  False     2   
14      Barbara Larsen        Auditor              True   True     3   
15         Peter Gomez  Undergraduate             False  False     4   
16        Anne Jimenez  Undergraduate             False   True     4   
17       Joshua Phelps       Graduate             False  False     0   
18          Erin Walls  Undergraduate             False  False     2   
19        Dakota Smith       Graduate             False  False     4   
20       Cheryl Strong  Undergraduate              True  False     3   
21          David Park        Auditor              True  False     2   
22  Mercedes Hernandez       Graduate              True  False     2   
23       Dawn Matthews        Auditor              True   True     2   
24    Kristina Pollard       Graduate             False  False     4   

    orientation_day                       email  \
0                 2       phyllis30@hotmail.com   
1                 1          nicole26@yahoo.com   
2                 4     carneycharles@gmail.com   
3                 5     glennjonathan@gmail.com   
4                 4     franklindylan@yahoo.com   
5                 4      wilsonlauren@yahoo.com   
6                 1            eric67@gmail.com   
7                 2     shawnwilliams@gmail.com   
8                 1          ugardner@yahoo.com   
9                 2            tara14@gmail.com   
10                3    williamsteresa@yahoo.com   
11                2         bernard01@gmail.com   
12                4       miranda28@hotmail.com   
13                2     gordonkelly@hotmail.com   
14                4   colemanbrittany@gmail.com   
15                4       william69@hotmail.com   
16                4           donna47@gmail.com   
17                3     shaneanderson@yahoo.com   
18                4  abigailrasmussen@gmail.com   
19                5   crawfordkaren@hotmail.com   
20                5            qburns@gmail.com   
21                1      jacqueline61@yahoo.com   
22                4  jennifermartinez@yahoo.com   
23                1            rgreen@gmail.com   
24                1         timothy45@yahoo.com   

                    Street Address                 City           State  \
0      3311 Wolfe Village Apt. 665            Scottland       Minnesota   
1      07259 Aaron Inlet Suite 959  New Jonathonborough    North Dakota   
2        138 Melinda Cape Apt. 342        New Scottstad       Wisconsin   
3      6393 Michael Inlet Apt. 222           Ashleyfurt        Colorado   
4               69799 Summers Wall          Walkershire   New Hampshire   
5                5744 Fields Plaza            East Leah      New Mexico   
6        397 Stacey Hills Apt. 147           Oscarshire           Maine   
7            30654 Cole Throughway             Leeville         Arizona   
8                6487 Sims Squares        Port Jennaton            Ohio   
9                 108 David Estate           Port Julia           Texas   
10                12909 Eric Lodge          East Taylor    Rhode Island   
11           2500 Mills Throughway        Lake Kimberly          Alaska   
12              3090 Davis Landing      Jenniferborough          Kansas   
13  80460 Joseph Crescent Apt. 334       Lake Ericaland       Minnesota   
14                977 Franco Wells        Port Jasonton        Kentucky   
15               478 Richard Lodge    West Rebeccamouth       Louisiana   
16     4727 Krystal Trace Apt. 211         East Patrick        Maryland   
17                69494 Amy Estate        West Alanberg            Ohio   
18        941 Jason Point Apt. 505        Hendersonfurt        Michigan   
19       292 Alexa Drive Suite 344      Port Kathyshire  South Carolina   
20               8963 Lawson Mills           Danielside         Florida   
21             9361 Foster Valleys           Rogersland            Iowa   
22  12559 Miller Highway Suite 290         West Michael    North Dakota   
23             1289 Bridges Drives        Lake Amyville        Nebraska   
24                046 Barber Grove           West Robin      New Mexico   

   ZIP Code  
0     91680  
1     91188  
2     07551  
3     12166  
4     87941  
5     94736  
6     51925  
7     61924  
8     57760  
9     67580  
10    67460  
11    80458  
12    83141  
13    65607  
14    06285  
15    04286  
16    94498  
17    92536  
18    53478  
19    29257  
20    49462  
21    55852  
22    77090  
23    59229  
24    71481  

Simulating dropouts

We are now goint to simulate two students, {python} admitted_students[3]

dropouts = [admitted_students[3], admitted_students[17]]

Making offers if places become available

This is now the final class after we had 2 dropouts.

                  name   student_type  computer_science   math  year  \
0        Sierra Thomas       Graduate              True  False     4   
1        Valerie Berry       Graduate              True   True     2   
2       Mallory Nelson  Undergraduate             False  False     4   
3        David Summers  Undergraduate              True   True     4   
4        Angela Burton       Graduate             False  False     2   
5      Melissa Kennedy        Auditor             False  False     2   
6            Paul Cook        Auditor             False  False     2   
7        Robert Chavez  Undergraduate             False  False     2   
8     Brandon Castillo        Auditor             False   True     2   
9      Michael Burgess  Undergraduate              True   True     4   
10        Jorge Miller       Graduate              True  False     3   
11      Dawn Gillespie       Graduate              True  False     4   
12       Sandra Hansen       Graduate             False  False     2   
13      Barbara Larsen        Auditor              True   True     3   
14         Peter Gomez  Undergraduate             False  False     4   
15        Anne Jimenez  Undergraduate             False   True     4   
16       Joshua Phelps       Graduate             False  False     0   
17          Erin Walls  Undergraduate             False  False     2   
18        Dakota Smith       Graduate             False  False     4   
19          David Park        Auditor              True  False     2   
20  Mercedes Hernandez       Graduate              True  False     2   
21       Dawn Matthews        Auditor              True   True     2   
22    Kristina Pollard       Graduate             False  False     4   
23      Gabrielle Dunn  Undergraduate              True  False     1   
24        Joseph Black        Auditor              True  False     1   

    orientation_day                       email  \
0                 2       phyllis30@hotmail.com   
1                 1          nicole26@yahoo.com   
2                 4     carneycharles@gmail.com   
3                 5     glennjonathan@gmail.com   
4                 4     franklindylan@yahoo.com   
5                 1            eric67@gmail.com   
6                 2     shawnwilliams@gmail.com   
7                 1          ugardner@yahoo.com   
8                 2            tara14@gmail.com   
9                 3    williamsteresa@yahoo.com   
10                2         bernard01@gmail.com   
11                4       miranda28@hotmail.com   
12                2     gordonkelly@hotmail.com   
13                4   colemanbrittany@gmail.com   
14                4       william69@hotmail.com   
15                4           donna47@gmail.com   
16                3     shaneanderson@yahoo.com   
17                4  abigailrasmussen@gmail.com   
18                5   crawfordkaren@hotmail.com   
19                1      jacqueline61@yahoo.com   
20                4  jennifermartinez@yahoo.com   
21                1            rgreen@gmail.com   
22                1         timothy45@yahoo.com   
23                1          tcarroll@yahoo.com   
24                1       holtlindsey@gmail.com   

                    Street Address                 City           State  \
0      3311 Wolfe Village Apt. 665            Scottland       Minnesota   
1      07259 Aaron Inlet Suite 959  New Jonathonborough    North Dakota   
2        138 Melinda Cape Apt. 342        New Scottstad       Wisconsin   
3      6393 Michael Inlet Apt. 222           Ashleyfurt        Colorado   
4               69799 Summers Wall          Walkershire   New Hampshire   
5        397 Stacey Hills Apt. 147           Oscarshire           Maine   
6            30654 Cole Throughway             Leeville         Arizona   
7                6487 Sims Squares        Port Jennaton            Ohio   
8                 108 David Estate           Port Julia           Texas   
9                 12909 Eric Lodge          East Taylor    Rhode Island   
10           2500 Mills Throughway        Lake Kimberly          Alaska   
11              3090 Davis Landing      Jenniferborough          Kansas   
12  80460 Joseph Crescent Apt. 334       Lake Ericaland       Minnesota   
13                977 Franco Wells        Port Jasonton        Kentucky   
14               478 Richard Lodge    West Rebeccamouth       Louisiana   
15     4727 Krystal Trace Apt. 211         East Patrick        Maryland   
16                69494 Amy Estate        West Alanberg            Ohio   
17        941 Jason Point Apt. 505        Hendersonfurt        Michigan   
18       292 Alexa Drive Suite 344      Port Kathyshire  South Carolina   
19             9361 Foster Valleys           Rogersland            Iowa   
20  12559 Miller Highway Suite 290         West Michael    North Dakota   
21             1289 Bridges Drives        Lake Amyville        Nebraska   
22                046 Barber Grove           West Robin      New Mexico   
23       75849 Mccoy Flat Apt. 194              Markton    Pennsylvania   
24        619 Ashlee Walk Apt. 251              Foxtown           Maine   

   ZIP Code  
0     91680  
1     91188  
2     07551  
3     12166  
4     87941  
5     51925  
6     61924  
7     57760  
8     67580  
9     67460  
10    80458  
11    83141  
12    65607  
13    06285  
14    04286  
15    94498  
16    92536  
17    53478  
18    29257  
19    55852  
20    77090  
21    59229  
22    71481  
23    07035  
24    52575  

Power BI Implementation

Power Bi - Data Model

Power Bi - Not Admitted Students

Power Bi - Admitted Students

Power Bi - Acceptance email